关于微信公众号

上周打的 ImaginaryCTF，比赛期间只做出了几道相对简单的密码学赛题，菜菜。复现的时候更是被狠狠的打击了。

rsa

题目给了三个文件，分别是 flag.enc；private.pem；public.pem；所以我们直接从 private.pem 里面导出私钥然后解密就可以了，基础操作题。

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes

key = RSA.importKey(open('private.pem', "rb").read())
flag = bytes_to_long(open("flag.enc", "rb").read())

print(long_to_bytes(pow(flag, key.d, key.n)))

emoticons

import random

emojis = [n for n in "🌸🍔🐳🚀🌞🎉🍦🎈🐶🍕🌺🎸⚡️🦋🌼🎁"]
m = open("text.txt", "rb").read().hex()

random.shuffle(emojis)

for e, c in zip(emojis, "0123456789abcdef"):
  m = m.replace(c, e)

open("out.txt", "w").write(m)

题目逻辑很简单，就是将明文编码成十六进制，然后使用类似于简单替换密码，将十六个字符随机映射到十六个emoji图案上。可以看到题目给的输出密文的数据量还是比较大的，所以其实考点应该就是简单的词频分析。

在比赛的时候有点猪脑过载，我就是一点点人工分析过来的，首先考虑 flag 的格式，”ictf{“.hex() == ‘696374667b’，然后我们在密文中找第0，2，6，7个字符相同，第4，8个字符相同的子串，会发现刚好只有一个，于是我们就能确定下来一些字符。然后根据已知的碎片信息一点点分析，在解题代码的注释中我列出了字符替换的逻辑。

with open("outs.txt","r",encoding = "utf-8") as f:
	data = f.read()
#print(len(data))

emojis = [n for n in "🌸🍔🐳🚀🌞🎉🍦🎈🐶🍕🌺🎸⚡🦋🌼🎁"]


# "ictf{".hex() ==  '696374667b'

for i in range(len(data)):
	sli = data[i:i+10]
	if sli[0] == sli[2] == sli[6] == sli[7] and sli[4] == sli[8]:
		print(i,sli)

🎈🐳🎈🌸🍕🎉🎈🎈🍕🎸

with open("outs.txt","r") as f:
	data = f.read()

data = data.replace("🎈","6").replace("🍕","7").replace("🐳","9").replace("🌸","3").replace("🎉","4").replace("🎸","b")


data = data.replace("🍦","a")						# 0a \m

data = data.replace("🎁","2").replace("🐶","0")		# 20 " "

data = data.replace("🦋","1").replace("🚀","c")		# 74797069636🦋6🚀6🚀79 typically

data = data.replace("🌼","5").replace("⚡","e")		# 77726974746🌼6⚡ written

data = data.replace("🌺","f")						# 6🌺6e6c696e65 online

data = data.replace("🍔","d")						# 656e7669726f6e6🍔656e742e 	environment.

data = data.replace("🌞","8")

PS：赛后看了官方解，只需要随便找一篇英文文章样例，十六进制编码后统计里面出现字符的频率，然后将这一题密文中各个emoji根据出现的频率排列，然后一一替换即可。

signer

import textwrap
from binascii import crc32
from Crypto.Util.number import getPrime

p, q = getPrime(1024), getPrime(1024)
n = p*q
e = 65537
d = pow(e, -1, (p-1)*(q-1))

PASSWORD = b"give me the flag!!!"

print("--------------------------------------------------------------")
print("               Welcome to the secure signing app!             ")
print("  I will sign whatever you want, except the secret password.  ")
print("--------------------------------------------------------------")
print()
print("--------------------------------------------------------------")
print("\n".join(textwrap.wrap(f"{n = }", len("-------------------------------------------------------------"))))
print("--------------------------------------------------------------")
print()

while True:
  print("1. Sign")
  print("2. Get flag")
  choice = int(input())

  if choice == 1:
    print("Enter message:")
    message = input().encode()
    # crc32 is secure and has no collisions, but just in case
    if message == PASSWORD or crc32(message) == crc32(PASSWORD):
      print("Stop this trickery!")
      exit()
    print("Signature:", pow(crc32(message), d, n))
  elif choice == 2:
    print("Enter the signature for the password:")
    s = int(input())
    if pow(s, e, n) == crc32(PASSWORD):
      print("You win! The flag is", open("flag.txt").read())
      exit()
    else:
      print("Wrong.")
      exit()

题目基于 RSA 签名系统，需要我们给出 PASSWORD = b"give me the flag!!!" 的签名，另外这里的签名不是对消息进行哈希，而是使用 crc32 来表示。我们知道 crc32 只有 4 个字节，因此这样一个多对一的映射在明文输入大于4个字节的时候是非常好碰撞的。所以这里首先计算 crc32(PASSWORD) 得到值 3542523789，不过由于限制

if message == PASSWORD or crc32(message) == crc32(PASSWORD):
  print("Stop this trickery!")
  exit()

我们不能直接输入PASSWORD，也不能输入和 PASSWORD 的 crc32 相等的消息。但是由于 RSA 具有乘法同态，所以我们可以先将 3542523789 分解为 13477 * 262857，然后分别碰撞出 crc32 等于 13477 和 262857 的两个消息，例如 2i_pQM 和 22p6NE。（crc32 碰撞的脚本还是比较好找的，毕竟是 MISC 中 zip 破解的一个考点）然后让服务器给这两条消息签名得到 $sig_1,sig_2$，然后计算 $sig_1\cdot sig_2 \pmod n$ 就是 PASSWORD 的签名了。发送给服务器就可以获得 flag 了。

tan

print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024))
# -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714

来自maple的 oneline crypto， $tan(flag) = c$，原本是 $tan$ 是可以由 $arctan$ 逆回去的，不过因为 $tan$ 函数的周期是 $2\pi$，所以 $arctan(c) \equiv flag \pmod{2\pi}$，写成等式有 $arctan(c) = flag + 2k \pi,k \in \mathbb{Z}$，

考虑构造格 $M =
\begin{bmatrix} arctan(c)& 1 & 0 & 0\newline\pi&0&1 & 0\newline 1&0&0 & 1 \newline
\end{bmatrix}$，会存在向量 $l = [-1 \ 2k \ flag]$ 使得 $l \times M = [0 \ -1 \ 2k \ flag]$，其实跟背包问题格子差不多。为了保证得到目标向量，我们也考虑给格子的第一列都乘上一个比较大的数，比如 $10^{307}$ 这样（刚好 $c$ 的小数点后面有307位）

c = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714
ac = atan(c)

shift = 10^307 
m=[[ac * shift,             1,0,0],
   [(pi.n(1024)) * shift,   0,1,0],
   [1  * shift,             0,0,1]]


M = matrix(QQ,m)
L = M.LLL()
long_to_bytes(abs(L[0][-1]))

# b'ictf{can_you_break_sin_or_cos_too?}'

PS：由于取整会导致误差，所以格基规约后矩阵的第一行向量的第一个元素并不是 0 。

wasteful

from Crypto.Util.number import *
from math import gcd


def keygen(sz):
    p = getPrime(sz // 2)
    q = getPrime(sz // 2)
    n = p * q
    phi = (p - 1) * (q - 1)
    e_fast = getPrime(sz // 2)
    # to make encryption more time consuming :P
    e_slow = e_fast + getPrime(sz // 3) * phi
    d = pow(e_fast, -1, phi)
    return (n, e_slow), (n, e_fast), (n, d)


def encrypt(pub, m):
    n, e = pub
    return pow(m, e, n)


def decrypt(priv, c):
    n, d = priv
    return pow(c, d, n)


pub, pub_fast, priv = keygen(2048)
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = encrypt(pub, m)
assert c == encrypt(pub_fast, m)
assert decrypt(priv, c) == m
print(f"{pub = }")
print(f"{c = }")

题目基于 RSA 公钥加密系统，$c \equiv m^e \pmod n$，给出了公钥对和密文 $c$。区别于正常的 RSA，这里给出的公钥指数是 $e’ = e + prime \cdot phi$，$prime$ 是一个 682 比特的素数。而 $e$ 本身也是一个 1024 比特的素数。

考虑组成 $e’$ 两项的大小关系，计算 $\frac{e’}{n}$，由于 $\varphi(n) \approx n$，所以 $\frac{e’}{n} \approx prime$，我们只需要在附近 $\pm10$ 的地方找一下就能找到 $prime$ 了。

随后我们计算 $e’//prime$ ( // 表示整除 )，由于 $phi$ 是2048 比特 $e$ 是 1024 比特，所以 $phi = e’//prime + \epsilon $ 其中 $\epsilon$ 可以看作一个 342比特的噪声。也就意味着我们能够知道 $phi$ 的高 1706 比特。根据 $phi = n + 1 - (p+q)$ 我们即可获取 $p+q$ 的高位，在使用一下平方差公式 $(p+q)^2 - 4n = (p-q)^2$，就能得到 $p-q$ 的高位，从而 $p = ((p+q)+(p-q))/2$ 得到 $p$ 的高位，然后利用 coppersmith 就能得到完整的 $p$，从而分解 $n$，解密得到 flag

from Crypto.Util.number import *
from gmpy2 import iroot
n,e = (, )
c = 
pr = e // n + 1
print(pr)
print(isPrime(pr))

phibar = e // pr
p_a_qbar = n+1-phibar
p_s_qbar = iroot((p_a_qbar**2-4*n),2)[0]
pbar = int((p_a_qbar+p_s_qbar)//2)

R.<x> = Zmod(n)[]
f = pbar + x
p0 = f.small_roots(X=2^400,beta=0.4)[0]
p = int(pbar+p0)
q = int(n//p)

d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))

# b'ictf{just_an_obligatory_coppersmith_challenge}'

以上就是比赛期间搞出来的五道题目了，猜牌游戏比赛的时候看了一半不太会，赛后对着官方 exp 尝试复现了下。

blind_guess

#!/usr/bin/env python3

from random import getrandbits
from galois import GF
import numpy as np

DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
F = GF(13) # lucky number
n = 10

# Let's not use a singular matrix, please.
# We do quality random over here.
M = [[0]]
while np.linalg.det(M) == 0:
    M = F.Random((n, n))

money = 15000
cards = F.Random(n)
while all(int(c) == 0 for c in cards):
    cards = F.Random(n)

while money > 0:
    print('balance:', money)
    choice = input('> ')

    if choice == 'buy flag':
        if money < 1_000_000_000:
            print("You're too poor!")
            continue

        from redacted import FLAG
        money -= 1_000_000_000
        print("What a guess god! Here's your flag:", FLAG)

    elif choice == 'play':
        bet = int(input('bet: '))
        assert money >= bet > 0
        print("Can you blindly guess my cards?")

        cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards  # shuffle cards
        guess = M @ F([*map(DECK.index, input('guess: ').split())]) # blind guess
        total = sum(cards == guess)

        print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])
        money += 2*(total - 5)*bet
    
    elif choice == 'exit':
        print("Chickened out, huh? No flag for you.")
        exit()

print("Woops... Looks like you guessed your way out of money :>")

题目是一个猜牌游戏，初始的拥有 15000 的 money，每一次猜牌可以自定义下注 bet，随后根据猜对的数量进行获利，获利规则为 2*(total - 5)*bet，即猜对六张及以上才可以获利。到 money 大于 1_000_000_000 后就可以获取 flag。

注意到每一次使用 $M^{random} \cdot cards$ 来“洗牌”，$cards$ 是上一轮的手牌，并且会在猜完后展示出来；$M$ 是一个行列式不为 0 的随机矩阵。$random$ 是由 getrandbits(32) 生成而来。那么思路就比较清晰了。

刚开始我们设 $bet=1$，然后就乱猜，主要目的就是看他的手牌，然后根据前后手牌的变化来 “想办法” 搞到这个 $random$，搞到 624 个之后我们就能够预测后续的 $random$，那个时候我们就一直 all in 就行了。

那么这个 “想办法” 该想什么样的办法呢，这是解题的关键，也是比赛的时候没想通的2333。如果我们能够知道 $M$ 和 $M^{random}$，那么我们就需要解一个矩阵的离散对数问题；这个好像可以取行列式来做，这样就转化为有限域下的离散对数问题了。那怎么搞到 $M$ 或者 $M$ 的行列式呢？

哎？注意到这个guess不是说你输入啥猜的就是啥，他会有一步处理，$guess = M \times input$，所以要满足的是 $M \times input = M ^{random} \times cards$。

那么，如果我们在输入的时候，构造的特殊一点，比如 input = [1 0 0 0 ...]，那么在经过 $M \times input$ 后，guess 的值就是 $M$ 第一列。不过我们不能直接获取到自己的 guess，只能根据最后展示的手牌和猜对的牌数来判断 guess 的值。那么怎么搞呢？撞！

guess 每个位置的牌都有 13 种可能，当前仅当猜对的总数为 0 的时候，我们就能够进行一次否定，可以保证每一个位置都不是所展示手牌的对应位置的牌。

当每个位置的可能都只剩 1 的时候，我们就获取了 $M$ 的一列值，然后进行下一列的撞。

(由于远程环境挂了，本地起 process 遇到点问题，就稍微改了改源代码在本地验证了)

from operator import lshift, rshift
from tqdm import trange
from random import getrandbits
from galois import GF
import numpy as np

DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
F = GF(13) # lucky number
n = 10

# Let's not use a singular matrix, please.
# We do quality random over here.
global M
M = [[0]]
while np.linalg.det(M) == 0:
    M = F.Random((n, n))

global money
money = 15000
global cards
cards = F.Random(n)
while all(int(c) == 0 for c in cards):
    cards = F.Random(n)

def local_game(choice,bet,inputs):
    
    global money
    global cards
    while money > 0:
        #print('balance:', money)

        if choice == 'buy flag':
            if money < 1_000_000_000:
                print("You're too poor!")
                continue

            from redacted import FLAG
            money -= 1_000_000_000
            print("What a guess god! Here's your flag:", FLAG)

        elif choice == 'play':
            assert money >= bet > 0
            #print("Can you blindly guess my cards?")
            
            cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards  # shuffle cards
            guess = M @ F([*map(DECK.index, inputs.split())]) # blind guess
            total = sum(cards == guess)

            #print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])
            money += 2*(total - 5)*bet
            return [int(c) for c in cards],total
        
        elif choice == 'exit':
            print("Chickened out, huh? No flag for you.")
            exit()

#print("Woops... Looks like you guessed your way out of money :>")

n = 10

hands = []
col = [set(range(13)) for _ in range(n)]
MM = []
i = 0
while i < n:
    guesscard = i*[0] + [1] + (n-i-1)*[0]
    hand, total = local_game('play',1, ' '.join(DECK[int(c)] for c in guesscard))
    hands.append(hand)
    if total == 0:
        for r, c in zip(col, hand):
            r.discard(c)

        if all(len(r) == 1 for r in col):
            MM.append([c for r in col for c in r])
            col = [set(range(13)) for _ in range(n)]
            i += 1
            print('i =', i)

print('M =', MM)
print(f"Collected {len(hands)} hands")

# M = [[2, 4, 3, 2, 5, 7, 9, 11, 7, 10], [12, 0, 7, 9, 1, 3, 0, 5, 5, 10], [0, 4, 1, 5, 10, 10, 5, 11, 2, 3], [4, 6, 5, 4, 2, 8, 0, 11, 0, 0], [12, 10, 8, 7, 12, 4, 10, 12, 3, 1], [6, 11, 2, 11, 7, 11, 10, 7, 12, 12], [2, 10, 1, 7, 2, 7, 0, 8, 1, 10], [10, 0, 8, 10, 12, 5, 4, 10, 5, 12], [10, 11, 8, 9, 11, 1, 9, 7, 5, 3], [11, 1, 8, 4, 3, 8, 6, 2, 11, 9]]
#　Collected 1403 hands

在大约经过1400 次暴力后我们能够拿到 $M$ ，不过想通过解离散对数获取 $random$ 的话，也还得获取到 $M^{random}$。根据题目我们有式子 $card_2 = M^{random} \cdot card_1$，由于线性代数学的一团糟，并不太知道接下来怎么搞，于是选择先“逃课”。根据 github 里巨人提供的板子

# https://github.com/jvdsn/crypto-attacks/blob/master/shared/matrices.py
def dlog_equation(A, x, y):
    """
    Computes l such that A^l * x = y, in GF(p).
    :param A: the matrix A
    :param x: the vector x
    :param y: the vector y
    :return: l, or None if l could not be found
    """
    assert A.is_square()

    # TODO: extend to GF(p^k) if necessary?
    J, P = A.jordan_form(transformation=True)
    x = P ** -1 * x
    y = P ** -1 * y
    r = 0
    for s1, s2 in zip(*J.subdivisions()):
        S = J.subdivision(s1, s2)
        assert S.is_square()

        n = S.nrows()
        r += n
        if n >= 2:
            x1 = x[r - 1]
            x2 = x[r]
            y1 = y[r - 1]
            y2 = y[r]
            l = S[n - 1, n - 1] * (y1 - x1 * y2 / x2) / y2
            return int(l)

    return None

利用我们前面一千四百多次的手牌和撞出来的 $M$ 直接调 dlog_equation 就能获取所有 $random$ 了，然后就是一个基础的 MT19937 状态恢复然后预测，这里就不过多赘述了。

不好意思，就到底为止了，后面的题目连题面都看不懂了，elf 文件,so 文件，factor 文件，wtf？？？？？？也许以后能看懂呢？也许叭…

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com